class Solution {
public:
    int left = 0, right = 0;
    string path;
    vector<string> ret;
    int num;

    vector<string> generateParenthesis(int n) {
        num = n;
        dfs();

        return ret;
    }

    void dfs()
    {
        if (right == num && left + right == 2 * num)
        {
            ret.push_back(path);
            return;
        }

        if (left < right || left > num) return;


        path += '(';
        left++;
        dfs();
        path.pop_back();
        left--;

        path += ')';
        right++;
        dfs();
        path.pop_back();
        right--;
    }
};